package 数据结构练习.summer;

import DataStructure_ZL.单行非循环链表.MySingleList;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class day9 {
    //链表准备
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    /*
    输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）
    https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
     */
   public int[] reversePrint(ListNode head) {
        //将所有的节点放入栈内然后再弹出栈将数据添加到数组中
        Stack<ListNode> iu=new Stack<>();
        ListNode cur=head;
        int size=0;
        while(cur!=null){
            iu.push(cur);
            cur=cur.next;
            size++;
        }
        int[] result=new int[size];
        for (int i = 0; i < size; i++) {
            result[i]=iu.pop().val;
        }
        return result;
    }

    /*
    编写代码，移除未排序链表中的重复节点。保留最开始出现的节点
    https://leetcode.cn/problems/remove-duplicate-node-lcci/
     */
   public ListNode removeDuplicateNodes(ListNode head) {
        //将数据存入集合当中如果包含就将节点删除
        Set<Integer> iu=new HashSet<>();
        ListNode cur=head;
        ListNode prev=head;
        while(cur!=null){
            if (!iu.contains(cur.val)){
                iu.add(cur.val);
                prev=cur;
            }else{
                prev.next=cur.next;
            }
            cur=cur.next;
        }
        return head;
    }
}
